Historically, mathematical analysis has often been used to determine the behavior of physical systems. Unsteady partial differential and/or integral equations are often utilized for that purpose. Examples of such equations commonly solved to determine the behavior of physical processes of physical systems include:                a) The Navier-Stokes equations for fluid flow, including the flow of air, water, and/or oil;        b) The Maxwell equations for electromagnetic propagation and radiation;        c) Chemical reaction equations such as those used for combustion;        d) Newton's equations for the motion of satellites and heavenly bodies;        e) The equations of structural dynamics for the deflections and vibration of structural members; and        f) The Boltzmann equations for molecular dynamics.        
The solutions of these equations are obtained in order to improve the manufacturing and/or engineering and/or performance of processes and/or products, such as quieter submarine propellers or helicopter rotors, quieter HVAC systems in buildings, more efficient engines, engines with lower emissions, more efficient airplane wings, improved electronic circuit boards, improved radar and sonar arrays, and improved aircraft structures, improved manufacturing processes, among others.
Because these equations typically do not have general analytic solutions, the equations are typically solved discretely on programmable computers. Other solution methods, such as using analog computers, have also been used to solve these equations.
There are many manufacturing processes and/or products whose performance and/or efficiency can be predicted by solving unsteady partial differential or integral equations. In these processes or products, an incremental increase in efficiency may have a very large impact on the costs of manufacturing and/or use over the life of the product; thus, fast and efficient solution procedures for unsteady partial differential or integral equations are useful to investigate possible improvements, for example, in efficiency.
In order to solve unsteady partial differential equations on computers, many solution techniques have been developed. To account for the time-dependent nature of the problem, at least two methods are currently used at the time of the writing of this application:
In the first method, the problem is solved by prescribing an analytic function for the time variation of the solution. For example, if the problem is periodic, a periodic function is substituted in for the unsteady terms in the partial differential equation. This approach is usually limited to linear problems with relatively simple solutions.
In the second, more commonly used method, no assumptions are made concerning the form of the time variation of the solution; instead, a local interpolant is used at each time level to represent the time variation of the solution. In this method, the spatial solution at a given time level is used to determine the instantaneous time rate of change of the solution at that time level, and the solution is discretely marched in time from that time level by using the time rate of change of the solution computed at each new time level to evolve the solution to the next time level.
This second method is much more general, but has deficiencies of its own. If the solution is being marched in time, the computer time required to solve a problem increases rapidly with the amount of resolution required to accurately represent the unsteady evolution of the solution; thus, if there is a region in the solution domain where the solution is rapidly changing in time, resolving the unsteadiness in this region by using smaller time steps will greatly increase the computer time required to solve the problem because all points in the solution domain will be marched at this small time step. Also, if the physical problem has a complex geometry which requires computational grids that are moving with respect to each other, the information transfer process at the interfaces between moving and stationary grids will require an interpolation method to be employed. Finally, the amount of parallelism in the problem is limited by the amount of spatial grid points at each time level; thus, solving the problem on parallel computers gives only a limited speedup.
A solution method for unsteady partial differential or integral equations that is general, allows for complex problems to be accurately and efficiently solved, and is parallel in nature is desired. This, in turn, allows manufacturers to improve the efficiency of both their manufacturing processes and the products themselves at a much lower cost than before.
An unsteady two-dimensional partial differential equation can be written in this form:
                                                        ∂              Q                                      ∂              t                                +                                    ∂              F                                      ∂              x                                +                                    ∂              G                                      ∂              y                                      =        S                            (        EQ1        )            
In EQ1, t represents time and x and y represent the Cartesian spatial dimensions. Q is the variable or variables to be solved for, representing the physical quantity or quantities of interest; here F, G, and S are functions of Q, x, y, and t. It is important to note that EQ1 is presented for illustrative purposes; unsteady partial differential equations may have more or fewer variables, more or fewer spatial dimensions, and more or fewer terms in the equations.
The Euler equations of fluid flow are one example of a commonly-used unsteady partial differential equation. The two-dimensional conservative Euler equations in Cartesian coordinates can be written as:
                                                                        ∂                                  ∂                  t                                            ⁢                              {                                                                            ρ                                                                                                                          ρ                        ⁢                                                                                                  ⁢                        u                                                                                                                                                ρ                        ⁢                                                                                                  ⁢                        v                                                                                                                        E                                                                      }                                      +                                          ∂                                  ∂                  x                                            ⁢                              {                                                                                                    ρ                        ⁢                                                                                                  ⁢                        u                                                                                                                                                                          ρ                          ⁢                                                                                                          ⁢                                                      u                            2                                                                          +                        p                                                                                                                                                ρ                        ⁢                                                                                                  ⁢                        uv                                                                                                                                                u                        ⁡                                                  (                                                      E                            +                            p                                                    )                                                                                                                    }                                      +                                          ∂                                  ∂                  y                                            ⁢                              {                                                                                                    ρ                        ⁢                                                                                                  ⁢                        v                                                                                                                                                ρ                        ⁢                                                                                                  ⁢                        uv                                                                                                                                                                          ρ                          ⁢                                                                                                          ⁢                                                      v                            2                                                                          +                        p                                                                                                                                                v                        ⁡                                                  (                                                      E                            +                            p                                                    )                                                                                                                    }                                              =          0                ,                            (                  EQ          ⁢                                          ⁢          2                )            where the Q vector consists of the density (ρ), the flow momentums in the x and y directions (ρu and ρv), and the total energy of the flow (E).
In order to solve an unsteady partial differential equation such as EQ1 on a computer, it is typically necessary to transform the analytic, continuous equations into their discrete numerical counterparts. In this way, instead of solving the equations everywhere, the solution is calculated only at specified points. To locate these points, a computational grid is generated. This grid covers the spatial domain, and usually contains, at most, only a few time levels. Given a grid, the discrete equations are then solved at every point or in every cell in the grid. If the differential form of the equations are to be solved, methods such as the spectral method or finite differences may be used to solve the differential equations. If the equations are to be solved in integral form, methods such as finite volume, finite element, lattice gas, or Direct Simulation Monte Carlo (DSMC) methods may be used to solve the integral equations. For illustration, finite differences will be used on the differential form of the equations; the other methods are direct extensions of this development, and are known in the art.
Using second order central finite differences in space and first-order backward finite differences in time, the derivatives at point (i,j,n) are written as:
                                                                                                                                    ∂                      Q                                                              ∂                      t                                                                                                          i                  ,                  j                  ,                  n                                            =                                                                    Q                                          i                      ,                      j                      ,                                              n                        +                        1                                                                              -                                      Q                                          i                      ,                      j                      ,                      n                                                                                        Δ                  ⁢                                                                          ⁢                  t                                                                                                                                                                                    ∂                      F                                                              ∂                      x                                                                                                          i                  ,                  j                  ,                  n                                            =                                                                    F                                                                  i                        +                        1                                            ,                      j                      ,                      n                                                        -                                      F                                                                  i                        -                        1                                            ,                      j                      ,                      n                                                                                        2                  ⁢                  Δ                  ⁢                                                                          ⁢                  x                                                                                                                                                                                    ∂                      G                                                              ∂                      y                                                                                                          i                  ,                  j                  ,                  n                                            =                                                                    G                                          i                      ,                                              j                        +                        1                                            ,                      n                                                        -                                      G                                          i                      ,                                              j                        -                        1                                            ,                      n                                                                                        2                  ⁢                  Δ                  ⁢                                                                          ⁢                  y                                                                                        (                  EQ          ⁢                                          ⁢          3                )            By using these particular finite difference representations, the local form of the solution is assumed to be a quadratic function in space and a linear function in time.
Note that the differencing method presented in EQ3 assumes a rectangular grid in the x and y directions with equal spacing between grid points in each direction. In EQ3, Δx is the spacing between grid points in the x direction, Δy is the spacing between grid points in the y direction, and Δt is the spacing between grid levels in time. Also, i is an index that represents grid points in the x-direction, j is an index that represents grid points in the y-direction, and n is an index that represents the time level.
Alternatively, if the problem has a known temporal variation T(t) and is linear, the variables may be separated as:Q(x,y,t)=q(x,y)T(t)F(x,y,t)=f(x,y)T(t)G(x,y,t)=g(x,y)T(t)S(x,y,t)=s(x,y)T(t)  (EQ4)and the equation rewritten as:
                                          q            ⁢                                          ∂                T                                            ∂                t                                              +                      T            ⁢                                          ∂                f                                            ∂                x                                              +                      T            ⁢                                          ∂                g                                            ∂                y                                                    =        sT                            (                  EQ          ⁢                                          ⁢          5                )            
Because T(t) is known, this reduces the equation from three dimensions to two and greatly speeds the solution process. However, the temporal variation is usually known beforehand only for very simple processes, and this method is not generally applicable. Thus, a time-marching procedure is usually used.
Using the differencing procedure from EQ3 in the partial differential equation presented in EQ1, a marching procedure in time can be written as:
                                                                                                                                    Q                                              i                        ,                        j                        ,                                                  n                          +                          1                                                                                      =                                                                  Q                                                  i                          ,                          j                          ,                          n                                                                    +                                              Δ                        ⁢                                                                                                  ⁢                                                                              t                            (                            S                                                                                                            i                            ,                            j                            ,                            n                                                                                              -                                                                        ∂                          F                                                                          ∂                          x                                                                                                                                                        i                  ,                  j                  ,                  n                                            -                                                ∂                  G                                                  ∂                  y                                                                                      i            ,            j            ,            n                          )                            (                  EQ          ⁢                                          ⁢          6                )            
The time marching procedure can be done either explicitly, using the solution at the current time level n to obtain the solution at the next time level:
                                                                                                                                    Q                                              i                        ,                        j                        ,                                                  n                          +                          1                                                                                      =                                                                  Q                                                  i                          ,                          j                          ,                          n                                                                    +                                              Δ                        ⁢                                                                                                  ⁢                                                                              t                            (                                                                                                                  ⁢                            S                                                                                                            i                            ,                            j                            ,                            n                                                                                              -                                                                        ∂                          F                                                                          ∂                          x                                                                                                                                                        i                  ,                  j                  ,                  n                                            -                                                ∂                  G                                                  ∂                  y                                                                                      i            ,            j            ,            n                          )                            (                  EQ          ⁢                                          ⁢          7                )            or implicitly, using the solution at the next time level n+1 to obtain the solution at the next time level:
                                                                                                                                    Q                                              i                        ,                        j                        ,                                                  n                          +                          1                                                                                      =                                                                  Q                                                  i                          ,                          j                          ,                          n                                                                    +                                              Δ                        ⁢                                                                                                  ⁢                                                                              t                            (                            S                                                                                                            i                            ,                            j                            ,                                                          n                              +                              1                                                                                                                          -                                                                        ∂                          F                                                                          ∂                          x                                                                                                                                                        i                  ,                  j                  ,                                      n                    +                    1                                                              -                                                ∂                  G                                                  ∂                  y                                                                                      i            ,            j            ,                          n              +              1                                      )                            (                  EQ          ⁢                                          ⁢          8                )            
Since the solution at the next time level is not known, either an iterative process or a direct solution of matrix equations is required to obtain the solution at the next time level. In an iterative process, an initial guess is made for the solution of the equations at the new time level. This initial solution is used to calculate an improved solution at the new time level, which is then used to calculate a more improved solution, and so on. This process continues until the difference in the input solution and the revised solution is small. An example of an iterative process is:
                                                                                                                                                                                      Q                                                      i                            ,                            j                            ,                                                          n                              +                              1                                                                                                            l                            +                            1                                                                          =                                                                              Q                                                          i                              ,                              j                              ,                                                              n                                +                                1                                                                                      l                                                    +                                                                                    ω                              (                              S                                                                                                                    i                              ,                              j                              ,                                                              n                                +                                1                                                                                      l                                                    -                                                                                    ∂                              Q                                                                                      ∂                              t                                                                                                                                                                                        i                      ,                      j                      ,                                              n                        +                        1                                                              l                                    -                                                            ∂                      F                                                              ∂                      x                                                                                                                  i                ,                j                ,                                  n                  +                  1                                            l                        -                                          ∂                G                                            ∂                y                                                                        i          ,          j          ,                      n            +            1                          l                            (                  EQ          ⁢                                          ⁢          9                )            where l and l+1 refer to the input solution and revised solution at the new time level n+1. Here, ω is a factor used to accelerate the convergence of the iterative process. Notice that the time derivative term has now been moved to the right-hand-side of the equation.
There are advantages and disadvantages to each method of time marching. The explicit time marching method requires much fewer calculations per time step, but the time step size Δt is limited by the grid spacing Δx and Δy due to numerical stability constraints. The implicit time marching methods used usually do not have the step size restriction, allowing fewer time steps, each of which require much more calculations to perform.
Since, for realistic problems, it is imperative that grid points be placed about complex geometries, and clustered in regions of interest, the equations are rewritten in a way that allows an arbitrary grid to be used. One way of accomplishing this, given for illustrative purposes, is by mapping the equations into generalized curvilinear coordinates (ξ,η,τ):ξ=ξ(x,y,t)η=η(x,y,t)τ=t  (EQ10)
Using the chain rule for derivatives, the equations can be rewritten as:
                                                        ∂              Q                                      ∂              τ                                +                                                    ∂                Q                                            ∂                ξ                                      ⁢                                          ∂                ξ                                            ∂                t                                              +                                                    ∂                Q                                            ∂                η                                      ⁢                                          ∂                η                                            ∂                t                                              +                                          ⁢                                                    ∂                F                                            ∂                ξ                                      ⁢                                          ∂                ξ                                            ∂                x                                              +                                                    ∂                F                                            ∂                η                                      ⁢                                          ∂                η                                            ∂                x                                              +                                                    ∂                G                                            ∂                ξ                                      ⁢                                          ∂                ξ                                            ∂                y                                              +                                                    ∂                G                                            ∂                η                                      ⁢                                          ∂                η                                            ∂                y                                                    =        S                            (                  EQ          ⁢                                          ⁢          11                )            
The equations are usually transformed into strongly conservative form to retain the numerical conservation properties of the original equation:
                                                        ∂                              ∂                τ                                      ⁢                          (                              Q                J                            )                                +                                          ⁢                                    ∂                              ∂                ξ                                      ⁢                          (                                                                                          ∂                      ξ                                                              ∂                      t                                                        ⁢                                      Q                    J                                                  +                                                                            ∂                      ξ                                                              ∂                      x                                                        ⁢                                      F                    J                                                  +                                                                            ∂                      ξ                                                              ∂                      y                                                        ⁢                                      G                    J                                                              )                                +                                          ⁢                                    ∂                              ∂                η                                      ⁢                          (                                                                                          ∂                      η                                                              ∂                      t                                                        ⁢                                      Q                    J                                                  +                                                                            ∂                      η                                                              ∂                      x                                                        ⁢                                      F                    J                                                  +                                                                            ∂                      η                                                              ∂                      y                                                        ⁢                                      G                    J                                                              )                                      =                  S          J                                    (                  EQ          ⁢                                          ⁢          12                )            where J is the Jacobian of the transformation, and is dependent on the grid metrics at each time level.
Again, these equations are usually marched in time, either explicitly or implicitly. For example, the implicit time marching method would be:
                                                                                                              Q                    J                                                                                      i                  ,                  j                  ,                                      n                    +                    1                                                                    l                  +                  1                                            =                              Q                J                                                                      i            ,            j            ,            n                    l                +                  ω          ⁡                      (                                                                                                                                                        S                          J                                                                                                                    i                        ,                        j                        ,                        n                                            l                                        -                                                                                                                                                                                                                        (                                                                      Q                                    J                                                                                                                                                                      i                                  ,                                  j                                  ,                                                                      n                                    +                                    1                                                                                                  l                                                            -                                                              Q                                J                                                                                                                                                                      i                            ,                            j                            ,                            n                                                                          )                                                                    Δ                        ⁢                                                                                                  ⁢                        t                                                                                                                                                              -                                                                                                                        (                                                                                                                                                                ∂                                    ξ                                                                                                        ∂                                    t                                                                                                  ⁢                                                                  Q                                  J                                                                                            +                                                                                                                                    ∂                                    ξ                                                                                                        ∂                                    x                                                                                                  ⁢                                                                  F                                  J                                                                                            +                                                                                                                                    ∂                                    ξ                                                                                                        ∂                                    y                                                                                                  ⁢                                                                  G                                  J                                                                                                                      )                                                                                                              i                              +                              1                                                        ,                            j                            ,                            n                                                    l                                                -                                                                              (                                                                                                                                                                ∂                                    ξ                                                                                                        ∂                                    t                                                                                                  ⁢                                                                  Q                                  J                                                                                            +                                                                                                                                    ∂                                    ξ                                                                                                        ∂                                    x                                                                                                  ⁢                                                                  F                                  J                                                                                            +                                                                                                                                    ∂                                    ξ                                                                                                        ∂                                    y                                                                                                  ⁢                                                                  G                                  J                                                                                                                      )                                                                                                              i                              -                              1                                                        ,                            j                            ,                            n                                                    l                                                                                            2                        ⁢                        Δ                        ⁢                                                                                                  ⁢                        ξ                                                                                                                                                              -                                                                                                                        (                                                                                                                                                                ∂                                    η                                                                                                        ∂                                    t                                                                                                  ⁢                                                                  Q                                  J                                                                                            +                                                                                                                                    ∂                                    η                                                                                                        ∂                                    x                                                                                                  ⁢                                                                  F                                  J                                                                                            +                                                                                                                                    ∂                                    η                                                                                                        ∂                                    y                                                                                                  ⁢                                                                  G                                  J                                                                                                                      )                                                                                i                            ,                                                          j                              +                              1                                                        ,                            n                                                    l                                                -                                                                              (                                                                                                                                                                ∂                                    η                                                                                                        ∂                                    t                                                                                                  ⁢                                                                  Q                                  J                                                                                            +                                                                                                                                    ∂                                    η                                                                                                        ∂                                    x                                                                                                  ⁢                                                                  F                                  J                                                                                            +                                                                                                                                    ∂                                    η                                                                                                        ∂                                    y                                                                                                  ⁢                                                                  G                                  J                                                                                                                      )                                                                                i                            ,                                                          j                              -                              1                                                        ,                            n                                                    l                                                                                            2                        ⁢                        Δ                        ⁢                                                                                                  ⁢                        η                                                                                                                  )                                              (                  EQ          ⁢                                          ⁢          13                )            
Note that in EQ13, the i index is now associated with the ξ direction, and the j index with the η direction. This is because the effect of the mapping is to transform an arbitrary grid in the physical plane (x,y,t) to a uniformly-spaced Cartesian grid in the computational plane (ξ,η,τ). It is important to note, however, that the n index is still associated with the time direction.
There are other methods of mapping the equations, such as spectral element, finite element, unstructured grid methods, or methods using cells such as lattice-gas or DSMC, but they share at least one attribute: The mapping methods all map the equations in space separately from time; thus, each space-time grid cell has at least one face that is normal to the time direction. To illustrate this, notice that in EQ12 the time direction τ has no transformation metrics; it is defined in EQ10 to be identical to the physical time.
In the prior art, there has been some investigation of the possibility of considering the unsteady problem as a space-time volume to be solved, instead of as a spatial volume to be marched in time. The concept of solving unsteady problems by gridding in space-time was initially published by Fried (1969), and the use of space-time grids to solve unsteady fluid, electromagnetic, and structural equations for ‘slabs’ of space-time has been gaining prominence since 1991. Some examples of the prior disclosures in this area are given in:                Fried, I. (1969) ‘Finite-Element Analysis of Time-Dependent Phenomena’, AIAA Journal, Vol. 7, No. 6, p. 1170-1173.        Shakib, F., Hughes, T. J. R., and Johan, Z. (1991) ‘A New Finite-Element Formulation for Computational Fluid Dynamics: X. The Compressible Euler and Navier-Stokes Equations’, Computer Methods in Applied Mechanics and Engineering, Vol. 89, p. 141-219;        Fijany, A., Jensen, M., Rahmat-Samii, Y., and Barhen, J. (1995) ‘A Massively Parallel Computation Strategy for FDTD: Time and Space Parallelism Applied to Electromagnetic Problems’, IEEE Transactions on Antennas and Propagation, Vol. 43, No. 12, p. 1441.        Zwart, P. J., Raithby, G. D., and Raw, M. J. (1998), ‘An Integrated Space-Time Finite Volume Method for Moving Boundary Problems’, AIAA Paper 98-0518.        Ray, S. E. (1998) ‘A Model for the Interaction of a Fluid with Multiple Deformable Bodies’, AIAA Paper 98-3155.        Behr, M. and Tezduyar, T. (1999) ‘The Shear-Slip Mesh Update Method’, Computer Methods in Applied Mechanics and Engineering, Vol 174, p. 261-274.        Dompierre, J., Labbe, P., Garon, A., and Camarero, R. (2000) ‘Unstructured Tetrahedral Mesh Adaptation for Two-Dimensional Space-Time Finite Elements’, AIAA Paper 2000-0810, 2000.        Dompierre, J., Labbe, P., Garon, A., and Camarero, R. (2000) ‘Unstructured Tetrahedral Mesh Adaptation for Two-Dimensional Space-Time Finite Elements’, AIAA Paper 2000-0810, 2000.        Behr, M. and Tezduyar, T. (2001) ‘Shear-Slip Mesh Update in 3D Computation of Complex Flow Problems with Rotating Mechanical Components’, Computer Methods in Applied Mechanics and Engineering, Vol. 190, p. 3189-3200.        Csik, A., Ricchiuto, M., Deconinck, H., and Poedts, S. (2001) ‘Space-Time Residual Distribution Schemes for Hyperbolic Conservation Laws’, AIAA Paper 2001-2617, 2001.        N'dri, D., Garon, A., and Fortin, A. (2001) ‘Analysis of Mixed and Stabilized Space-Time Finite-Element Methods for the Navier-Stokes Equations’, AIAA Paper 2001-0280, 2001.        Udoewa, V., Keedy, R., Tezduyar, T., Nonoshita, T., Stein, K., Benney, R., and Johnson, A. (2001) ‘Computational Aerodynamics of a Paratrooper Separating from an Aircraft’, AIAA Paper 2001-2067, 2001.        Ray, Stephen E. (2000) ‘A Model of Fluid-Structure Interactions Including Contact for Interior Flow Applications’, AIAA Paper 2000-2340, 2000.        
However, one thing that is common to all of the above, along with most other previous approaches, is that the space-time grids always have a well-defined time direction, wherein each space-time grid cell has at least one face that is normal to the time direction.
This feature of the mapping has a direct impact on the grids, and hence the methods that are currently used to discretely solve unsteady partial differential equations. The effect that this mapping has on the current methods of solving problems of practical interest is illustrated in the following examples:                a) Processes with a wide range of length and time scales. An example of this type of process would be the determination of the flow and noise produced in an automobile ventilation system duct. In this case, the flow in the center of the duct will be relatively smooth and uniform, being affected by the geometry of the duct. In contrast, the flow near the duct wall will be highly turbulent, with many tiny eddies and vortices. This region of the flow will determine if the main flow in the duct separates from the wall as the duct turns. The resulting separation bubble will reduce the flow through the duct and generate a large amount of noise. To accurately calculate a flow of this nature requires the highly unsteady flow near the wall to be well resolved in space and time; this results in very small grid spacing near the wall and very small time steps. Using currently available technology, there are two choices: either the entire spatial domain is marched at the small time step, or a multiple-time-stepping method is used. Marching the entire domain at the small time step requires a very large amount of computer time, which is undesirable. Using a multiple-time-stepping method allows each region of the grid to be marched at different time steps and synchronized occasionally. This reduces the amount of CPU time required. However, this method introduces computer logic and interpolation issues and is not easily parallelized; thus it has been rarely used.        b) Processes with moving and stationary bodies. An example of this type of problem would be the bypass flow in a jet aircraft engine. In a jet engine, there is flow that enters the engine inlet, but does not have fuel added. This flow is spun and given thrust from a large spinning fan (the rotor), and the flow is straightened to exit the engine cleanly by a stationary blade row (the stator). The engine performance and noise radiation is dependent on the design of the rotor/stator combination. To calculate the flow through this geometry, two grids are usually generated. The first grid is attached to the rotor, and spins with it. The second grid is attached to the stator, and is stationary. Where the two grids meet, one grid is spinning, while the other is stationary; thus, at each time level, the spinning grid has moved with respect to the stationary grid at the interface where they meet. In order to accurately calculate the flow through this grid interface, information must be transferred between the two grids at each time level. Since the grids are moving with respect to each other, an interpolation process must be used at each time step in order to transfer data accurately between the two grids. This interpolation process requires special computer programs to be written and used, and this process adds computer time and complexity to the solution procedure. In existing codes, this interpolation process limits the time step below the time step that the code could normally use, and hence adds to the solution time required. Another group of methods, used in finite-element and finite-volume approaches, use a space-time approach to gridding and solving problems of this class. In the space-time approach, the problem is divided into ‘slabs’ of space-time volume, each of which contain two or more time levels (the ‘n’ and ‘n+1’ levels). Each space-time slab allows the spatial grid to change the number and location of grid points from the nth time level to the (n+1st) time level. While this method does allow the possibility of generating grids which do not require interpolation, generating these grids is a highly complex problem, and the method is not widely used.        c) Processes where the flow in a small region over a short period of time completely determines the resulting performance. An example of this type of problem is the aerodynamic performance of a fighter aircraft that is pitching up rapidly. In this maneuver, the aircraft can dynamically generate a large amount of lift and climb very rapidly before the aircraft stalls and loses lift (dynamic stall). This stall process begins when the flow separates near the leading edge of the wing, forming a small separation bubble. The separation bubble quickly spreads across the upper surface of the wing, and the lift is sharply reduced. The area of separation, and the rate at which it spreads, is influenced greatly by the initial separation bubble, which is very small and occurs very quickly. The unknown location and formation time of the initial separation bubble makes this flow very difficult to compute accurately. Since the existing unsteady methods march in time, there is only one opportunity to capture the location and dynamics of the separation bubble. In order to ensure that this occurs, a very dense grid and a very small time step must be used, adding greatly to the computer time required for this problem. Again, if a single-time-stepping method is used, all of the grid points in the entire grid must be updated for each very small time step even though only the points in close proximity to the separation bubble require such high resolution. Even with a multiple-time-stepping method, the region of high resolution must be continuously expanded as the separation bubble grows, adding great complexity to the process.        d) Processes where two or more sets of governing equations interact. An example of this would be the problem of aircraft wing flutter. In this process, the lift on the wing of an airplane causes the wing to bend, which then reduces the lift, allowing the wing to spring back, which then causes the wing to produce more lift and bend upward again. This process can repeat until the wing fails. To calculate the dynamic flutter of a wing, both the Navier-Stokes equations for the flow around the wing and the structural equations for the deflections of the wing structure itself must be calculated simultaneously, and the solutions of each equation affects the other. To do this, both equations are solved at each time step, with the resulting wing motion used to recalculate the grid for the aerodynamic solver. This type of calculation can take a very long time to converge to a limit cycle using a time marching approach.        e) Processes where all of the above occur. In a worst case, all of these problems occur. A common process which contains all of these problems is the flow and combustion inside an four-stroke reciprocating internal combustion engine. First, the range of time and length scales is very large, due to the extreme rapidity with which combustion occurs. The flow is moving at the speed of the piston, which is at most 20 meters per second but is near zero as the piston nears the top of its stroke, while the combustion flame front moves at a supersonic speed during detonation, which is greater than 1500 meters per second. The time scales are even more disparate, as combustion occurs very rapidly. Thus, the problem must be done either with multiple-time-stepping with their added complexity or implicit methods with their loss of accuracy. Second, there are moving and stationary bodies which must have grids wrapped around them to accurately account for the effect of these bodies on the flow. The piston is moving up and down in the stationary cylinder, and the intake and exhaust valves are opening and closing in the stationary cylinder head. The gridding and interpolation issues for the engine cycle are thus very complex and time-consuming. Again, the interpolation issues could be avoided by using the space-time mapping methods discussed in Example (b) above, but at a cost of higher grid complexity. Third, the combustion process has a very large effect on the pollution and performance produced by the engine. Combustion begins in a very small region near the spark plug, and the flame front rapidly expands throughout the cylinder. However, if there are hot spots in the cylinder, detonation may occur at the hot spot, causing another ignition source and flame front. The propagation of the flame front is also complex. The flame front is not a smooth sphere; instead, it is wrinkled locally due to turbulence in the cylinder. This turbulence accelerates or decelerates the flame front, and has an effect on the total performance of the engine. To capture this process requires a very small time step and a large number of grid points—and thus a very long computer run time. Fourth, the piston motion is determined from the pressures in the cylinder; thus, the structural equations of motion must be solved in parallel with the combustion equations and the Navier-Stokes equations for the flow. These problems make the calculation of the performance of an internal combustion engine very complex and time-consuming, and there are very few computer codes which can do this with high accuracy.        